package leetcode.ch02_链表;

/**
 *
 * https://leetcode-cn.com/problems/remove-linked-list-elements/
 * 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
 *
 * @author guodd
 * @version 1.0 use jdk 1.8
 */
public class _203_移除链表元素 {
    public ListNode removeElements(ListNode head, int val) {
        // 01如果head值就是val,且不是空进行删除操作，如果删除后新的节点值也是val，所以需要循环
        while (head != null && head.val == val) {
            ListNode delNode = head;
            head = head.next;
            delNode.next = null;
        }
        // 02如果经过01步骤元素全部删除了，直接返回
        if (head == null) {
            return null;
        }
        // 03进行不是头节点的删除
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == val) {
                // 要删除的元素
                ListNode delNode = prev.next;
                // 绕开要删除的元素
                prev.next = delNode.next;
                // 断掉联系
                delNode.next = null;
            } else {
                prev = prev.next;
            }
        }
        return head;
    }

    public ListNode removeElements01(ListNode head, int val) {
        // 01创建虚拟头节点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        // 02
        ListNode prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }

    public ListNode removeElements02(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        // 子过程的宏观语义是：删除值为val的节点
        ListNode node = removeElements02(head.next, val);
        if (head.val == val) {
            return node;
        } else {
            head.next = node;
            return head;
        }
    }

    public ListNode removeElements03(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        head.next = removeElements03(head.next, val);
        return head.val == val ? head.next : head;
    }
}
